{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import re\n",
    "import os\n",
    "from glob import glob\n",
    "import shutil\n",
    "import sys\n",
    "import json\n",
    "import time\n",
    "import datetime\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import cv2\n",
    "import matplotlib.pyplot as plt \n",
    "from PIL import Image\n",
    "%matplotlib inline\n",
    "# 这两行代码解决 plt 中文显示的问题\n",
    "plt.rcParams['font.sans-serif'] = ['SimHei']\n",
    "plt.rcParams['axes.unicode_minus'] = False\n",
    "\n",
    "path = r\"D:\\work space\\git\\ImageProcessing100Wen\\Question_91_100\"\n",
    "img_path = os.path.join(path, 'imori_many.jpg')\n",
    "np.random.seed(0)\n",
    "# img_path\n",
    "def plt_img(img):\n",
    "    cv2.imwrite(\"out.jpg\", img)\n",
    "    img = Image.open(\"out.jpg\")\n",
    "    img = np.array(img)\n",
    "    plt.imshow(img)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "从这⾥开始进⾏物体检测吧！\n",
    "物体检测是检测图像中到底有什么东⻄的任务。例如，图像在 处有⼀只狗。像这样把物体圈出来的矩形我们称之为\n",
    "Bounding-box。\n",
    "下⾯实现简单物体检测算法：\n",
    "1. 从图像左上⻆开始进⾏滑动窗⼝扫描；\n",
    "2. 在滑动的过程中，会依次圈出很多矩形区域；\n",
    "3. 裁剪出每个矩形区域对应的图像，并对裁剪出的图像提取特征（HOG，SIFT等）；\n",
    "4. 使⽤分类器（CNN，SVM等）以确定每个矩形是否包含⽬标。\n",
    "这样做的话，会得到⼀些裁剪过的图像和其对应的矩形的坐标。⽬前，物体检测主要通过深度学习（Faster R-CNN、YOLO、SSD等）进\n",
    "⾏，但是这种滑动窗⼝⽅法在深度学习开始流⾏之前已成为主流。为了学习检测的基础知识我们使⽤滑动窗⼝来进⾏检测。\n",
    "我们实现步骤1⾄步骤3。\n",
    "\n",
    "矩形使⽤以下⽅法表示：\n",
    "滑动步⻓为4个像素（每次滑动⼀个像素固然是好的，但这样需要⼤量计算，处理时间会变⻓）；\n",
    "如果矩形超过图像边界，改变矩形的形状使其不超过图像的边界；\n",
    "将裁剪出的矩形部分⼤⼩调整为 ；\n",
    "计算HOG特征值时 cell ⼤⼩取 。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# get HOG\n",
    "def HOG(img):\n",
    "    # Grayscale\n",
    "    def BGR2GRAY(img):\n",
    "        gray = 0.2126 * img[..., 2] + 0.7152 * img[..., 1] + 0.0722 * img[..., 0]\n",
    "        return gray\n",
    "\n",
    "    # Magnitude and gradient\n",
    "    def get_gradXY(gray):\n",
    "        H, W = gray.shape\n",
    "\n",
    "        # padding before grad\n",
    "        gray = np.pad(gray, (1, 1), 'edge')\n",
    "\n",
    "        # get grad x\n",
    "        gx = gray[1:H+1, 2:] - gray[1:H+1, :W]\n",
    "        # get grad y\n",
    "        gy = gray[2:, 1:W+1] - gray[:H, 1:W+1]\n",
    "        # replace 0 with \n",
    "        gx[gx == 0] = 1e-6\n",
    "\n",
    "        return gx, gy\n",
    "\n",
    "    # get magnitude and gradient\n",
    "    def get_MagGrad(gx, gy):\n",
    "        # get gradient maginitude\n",
    "        magnitude = np.sqrt(gx ** 2 + gy ** 2)\n",
    "\n",
    "        # get gradient angle\n",
    "        gradient = np.arctan(gy / gx)\n",
    "\n",
    "        gradient[gradient < 0] = np.pi / 2 + gradient[gradient < 0] + np.pi / 2\n",
    "\n",
    "        return magnitude, gradient\n",
    "\n",
    "    # Gradient histogram\n",
    "    def quantization(gradient):\n",
    "        # prepare quantization table\n",
    "        gradient_quantized = np.zeros_like(gradient, dtype=np.int)\n",
    "\n",
    "        # quantization base\n",
    "        d = np.pi / 9\n",
    "\n",
    "        # quantization\n",
    "        for i in range(9):\n",
    "            gradient_quantized[np.where((gradient >= d * i) & (gradient <= d * (i + 1)))] = i\n",
    "\n",
    "        return gradient_quantized\n",
    "\n",
    "\n",
    "    # get gradient histogram\n",
    "    def gradient_histogram(gradient_quantized, magnitude, N=8):\n",
    "        # get shape\n",
    "        H, W = magnitude.shape\n",
    "\n",
    "        # get cell num\n",
    "        cell_N_H = H // N\n",
    "        cell_N_W = W // N\n",
    "        histogram = np.zeros((cell_N_H, cell_N_W, 9), dtype=np.float32)\n",
    "\n",
    "        # each pixel\n",
    "        for y in range(cell_N_H):\n",
    "            for x in range(cell_N_W):\n",
    "                for j in range(N):\n",
    "                    for i in range(N):\n",
    "                        histogram[y, x, gradient_quantized[y * 4 + j, x * 4 + i]] += magnitude[y * 4 + j, x * 4 + i]\n",
    "\n",
    "        return histogram\n",
    "\n",
    "\t\t# histogram normalization\n",
    "    def normalization(histogram, C=3, epsilon=1):\n",
    "        cell_N_H, cell_N_W, _ = histogram.shape\n",
    "        ## each histogram\n",
    "        for y in range(cell_N_H):\n",
    "    \t    for x in range(cell_N_W):\n",
    "       \t    #for i in range(9):\n",
    "                histogram[y, x] /= np.sqrt(np.sum(histogram[max(y - 1, 0) : min(y + 2, cell_N_H),\n",
    "                                                            max(x - 1, 0) : min(x + 2, cell_N_W)] ** 2) + epsilon)\n",
    "\n",
    "        return histogram\n",
    "\n",
    "    # 1. BGR -> Gray\n",
    "    gray = BGR2GRAY(img)\n",
    "\n",
    "    # 1. Gray -> Gradient x and y\n",
    "    gx, gy = get_gradXY(gray)\n",
    "\n",
    "    # 2. get gradient magnitude and angle\n",
    "    magnitude, gradient = get_MagGrad(gx, gy)\n",
    "\n",
    "    # 3. Quantization\n",
    "    gradient_quantized = quantization(gradient)\n",
    "\n",
    "    # 4. Gradient histogram\n",
    "    histogram = gradient_histogram(gradient_quantized, magnitude)\n",
    "    \n",
    "    # 5. Histogram normalization\n",
    "    histogram = normalization(histogram)\n",
    "\n",
    "    return histogram\n",
    "\n",
    "\n",
    "# get IoU overlap ratio\n",
    "def iou(a, b):\n",
    "\t# get area of a\n",
    "    area_a = (a[2] - a[0]) * (a[3] - a[1])\n",
    "\t# get area of b\n",
    "    area_b = (b[2] - b[0]) * (b[3] - b[1])\n",
    "\n",
    "\t# get left top x of IoU\n",
    "    iou_x1 = np.maximum(a[0], b[0])\n",
    "\t# get left top y of IoU\n",
    "    iou_y1 = np.maximum(a[1], b[1])\n",
    "\t# get right bottom of IoU\n",
    "    iou_x2 = np.minimum(a[2], b[2])\n",
    "\t# get right bottom of IoU\n",
    "    iou_y2 = np.minimum(a[3], b[3])\n",
    "\n",
    "\t# get width of IoU\n",
    "    iou_w = iou_x2 - iou_x1\n",
    "\t# get height of IoU\n",
    "    iou_h = iou_y2 - iou_y1\n",
    "\n",
    "\t# get area of IoU\n",
    "    area_iou = iou_w * iou_h\n",
    "\t# get overlap ratio between IoU and all area\n",
    "    iou = area_iou / (area_a + area_b - area_iou)\n",
    "\n",
    "    return iou\n",
    "\n",
    "# resize using bi-linear\n",
    "def resize(img, h, w):\n",
    "    # get shape\n",
    "    _h, _w, _c  = img.shape\n",
    "\n",
    "    # get resize ratio\n",
    "    ah = 1. * h / _h\n",
    "    aw = 1. * w / _w\n",
    "\n",
    "    # get index of each y\n",
    "    y = np.arange(h).repeat(w).reshape(w, -1)\n",
    "    # get index of each x\n",
    "    x = np.tile(np.arange(w), (h, 1))\n",
    "\n",
    "    # get coordinate toward x and y of resized image\n",
    "    y = (y / ah)\n",
    "    x = (x / aw)\n",
    "\n",
    "    # transfer to int\n",
    "    ix = np.floor(x).astype(np.int32)\n",
    "    iy = np.floor(y).astype(np.int32)\n",
    "\n",
    "    # clip index\n",
    "    ix = np.minimum(ix, _w-2)\n",
    "    iy = np.minimum(iy, _h-2)\n",
    "\n",
    "    # get distance between original image index and resized image index\n",
    "    dx = x - ix\n",
    "    dy = y - iy\n",
    "\n",
    "    dx = np.tile(dx, [_c, 1, 1]).transpose(1, 2, 0)\n",
    "    dy = np.tile(dy, [_c, 1, 1]).transpose(1, 2, 0)\n",
    "    \n",
    "    # resize\n",
    "    out = (1 - dx) * (1 - dy) * img[iy, ix] + dx * (1 - dy) * img[iy, ix + 1] + (1 - dx) * dy * img[iy + 1, ix] + dx * dy * img[iy + 1, ix + 1]\n",
    "    out[out > 255] = 255\n",
    "\n",
    "    return out\n",
    "\n",
    "# sliding window\n",
    "def sliding_window(img, H_size=32):\n",
    "    # get shape\n",
    "    H, W, _ = img.shape\n",
    "    \n",
    "    # base rectangle [h, w]\n",
    "    recs = np.array(((42, 42), (56, 56), (70, 70)), dtype=np.float32)\n",
    "\n",
    "    # sliding window\n",
    "    for y in range(0, H, 4):\n",
    "        for x in range(0, W, 4):\n",
    "            for rec in recs:\n",
    "                # get half size of ractangle\n",
    "                dh = int(rec[0] // 2)\n",
    "                dw = int(rec[1] // 2)\n",
    "\n",
    "                # get left top x\n",
    "                x1 = max(x - dw, 0)\n",
    "                # get left top y\n",
    "                x2 = min(x + dw, W)\n",
    "                # get right bottom x\n",
    "                y1 = max(y - dh, 0)\n",
    "                # get right bottom y\n",
    "                y2 = min(y + dh, H)\n",
    "\n",
    "                # crop region\n",
    "                region = img[max(y - dh, 0) : min(y + dh, H), max(x - dw, 0) : min(x + dw, W)]\n",
    "\n",
    "                # resize crop region\n",
    "                region = resize(region, H_size, H_size)\n",
    "\n",
    "                # get HOG feature\n",
    "                region_hog = HOG(region).ravel()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read detect target image\n",
    "img = cv2.imread(img_path)\n",
    "sliding_window(img)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "4\n",
      "8\n",
      "12\n",
      "16\n",
      "20\n",
      "24\n",
      "28\n"
     ]
    }
   ],
   "source": [
    "for y in range(0, 32, 4):\n",
    "    print(y)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
